#include<bits/stdc++.h>
#define N 200005
using namespace std;
struct nd
{
    int a,b;
    nd(int a=0,int b=0):a(a),b(b){}
    bool operator<(nd k)
    {
        return a>k.a;
    }
};
int mp[1000005],s[1000005],e[1000005],sv1[N],sv2[N];;
int a[N];
vector<nd>ans;
bool check1(int ss,int ee)
{
    for(int i=ss;i<=ee;i++)
    {
        if(sv1[i]==1)return 0;
    }
    for(int i=ss;i<=ee;i++)
    {
        sv1[i]=1;
    }
    return 1;
}
bool check2(int ss,int ee)
{
    for(int i=ss;i<=ee;i++)
    {
        if(sv2[i]==1)return 0;
    }
    for(int i=ss;i<=ee;i++)
    {
        sv2[i]=1;
    }
    return 1;
}
void solve()
{
    ans.clear();
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
        if(!mp[a[i]])
        {
            s[a[i]]=i;
        }
        mp[a[i]]++;
        e[a[i]]=i;
    }
    for(int i=1;i<=n;i++)
    {
        if(mp[a[i]]>1)
        {
            ans.push_back(nd(a[i]*(mp[a[i]]-1),a[i]));
            mp[a[i]]=0;
        }
    }
    int sum=0;
    sort(ans.begin(),ans.end());
    for(int i=0;i<ans.size();i++)
    {
        if(check1(s[ans[i].b],e[ans[i].b]))
        {
            sum+=ans[i].a;
            s[ans[i].b]=0;
            e[ans[i].b]=0;
        }
        else if(check2(s[ans[i].b],e[ans[i].b]))
        {
            sum+=ans[i].a;
        }
    }
    for(int i=1;i<=n;i++)sv1[i]=0,sv2[i]=0;
    cout<<sum<<endl;
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    int T;
    cin>>T;
    while(T--)
    {
        solve();
    }
    return 0;
}
